package com.github.hgkmail.hello.leetcode101.dualpointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LC524LongestWordInDictionaryThroughDeleting {
    public String findLongestWord(String s, List<String> dictionary) {
        //base case
        int sz=dictionary.size();
        if (s.length()<=0 || sz<=0) {
            return "";
        }
        char[] sChars = s.toCharArray();
        String resStr="";
        for (int k = 0; k < sz; k++) {
            char[] tChars = dictionary.get(k).toCharArray();
            int i=0;
            int j=0;
            //双指针
            while (i<sChars.length && j<tChars.length) {
                if (sChars[i]==tChars[j]) {
                    i+=1;
                    j+=1;
                } else {
                    i+=1;
                }
            }
            if (j>=tChars.length) {
                String tStr = dictionary.get(k);
                if (tStr.length()>resStr.length()) {
                    resStr = tStr;
                } else if (tChars.length==resStr.length() && tStr.compareTo(resStr)<0) { //长度相同，取字母序小的
                    resStr = tStr;
                }
            }
        }
        return resStr;
    }
    public static void main(String[] args) {
        String s="abpcplea";
        List<String> dictionary = new ArrayList<>();
        dictionary.add("abe");
        dictionary.add("abc");
        System.out.println(new LC524LongestWordInDictionaryThroughDeleting().findLongestWord(s,dictionary));
    }
}
